package com.sunny.l24;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public class Solution {

    public static void main(String[] args) {

//        Node node1 = new Node("aaa",1);
//        Node node2 = new Node("bbb",1);
//        ArrayList<Node> list = new ArrayList<>();
//        list.add(node1);
//        list.add(node2);
//        Collections.sort(list);
//        list.forEach(System.out::println);

        String start = "hit";
        String end = "cog";
        List<String> dict = new ArrayList<>(Arrays.asList("hot","dot","dog","lot","log","cog"));
        Solution solution = new Solution();
        List<List<String>> res = solution.findLadders(start, end, dict);


        System.out.println(res);
    }

//    public List<List<String>> findLadders(String start, String end, HashSet<String> dict) {
//        HashMap<String, ArrayList<String>> map = pre(start, end, dict);
//
//        return dfs(start, end, map);
//    }
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord))
            return new ArrayList<>();
        HashMap<String, ArrayList<String>> map = pre(beginWord, endWord, wordList);

        return dfs(beginWord, endWord, map);
    }

    public List<List<String>> dfs(String start, String end, HashMap<String, ArrayList<String>> map){
        List<List<String>> res = new ArrayList<>();
        if(start.equals(end)){
            ArrayList<String> list = new ArrayList<>();
            list.add(end);
            res.add(list);
            return res;
        }
        for(String str: map.get(start)) {
            List<List<String>> nres = dfs(str, end, map);
//            System.out.println(nres);
            for(List<String> l: nres){
                ArrayList<String> list = new ArrayList<>();
                list.add(start);
                list.addAll(l);
                res.add(list);
            }

        }
        return res;
    }

    //bfs预处理
    public HashMap<String, ArrayList<String>> pre(String start, String end, List<String> dict){
//        if(!dict.contains(end))
//            dict.add(end);
        HashMap<String, ArrayList<String>> res = new HashMap<>();
        LinkedBlockingQueue<String> queue1 = new LinkedBlockingQueue<>();
        LinkedBlockingQueue<String> queue2 = new LinkedBlockingQueue<>();
        int tag = 1;
        queue1.offer(start);
        ArrayList<String> removeList1 = new ArrayList<>();
        removeList1.add(start);
        ArrayList<String> removeList2 = new ArrayList<>();
        while ( (1 == tag && !queue1.isEmpty()) || (2 == tag && !queue2.isEmpty())){
            ArrayList<String> list = new ArrayList<>();
            if(1 == tag){
                String tmp = queue1.poll();
                for(String n: dict){
                    int tmpDigit = getDigit(tmp, n);
                    if(removeList1.contains(n) || -1 == tmpDigit){
                        continue;
                    }
                    list.add(n);
                    removeList2.add(n);
                    queue2.offer(n);
                }
                if(!res.containsKey(tmp)){
                    list.sort((o1, o2) -> o2.compareTo(o1));
                    res.put(tmp, list);
                }
                if(queue1.isEmpty()) {
                    dict.removeAll(removeList1);
                    removeList1.clear();
                    tag = 2;
                }
            }else{
                String tmp = queue2.poll();
                for(String n: dict){
                    int tmpDigit = getDigit(tmp, n);
                    if(removeList2.contains(n) || -1 == tmpDigit){
                        continue;
                    }
                    list.add(n);
                    removeList1.add(n);
                    queue1.offer(n);
                }
                if(!res.containsKey(tmp)){
                    list.sort((o1, o2) -> o2.compareTo(o1));
                    res.put(tmp, list);
                }
                if(queue2.isEmpty()){
                    dict.removeAll(removeList2);
                    removeList2.clear();
                    tag = 1;
                }
            }
        }
        return res;
    }

    public int getDigit(String str, String next){
        int cnt = 0;
        int digit = -1;
        for(int i=0;i<str.length();i++){
            if(str.charAt(i) != next.charAt(i)){
                cnt++;
                if(digit == -1)
                    digit = i;
            }
        }
        if(cnt > 1){
            return -1;
        }
        return digit;
    }
}
